package top.minuy.structure.graph.mst;

import top.minuy.structure.graph.cc.bfs.WeightedCC;
import top.minuy.structure.graph.representations.WeightedEdge;
import top.minuy.structure.graph.representations.table.WeightedGraph;
import top.minuy.structure.queue.PriorityQueueMin;

import java.util.ArrayList;
import java.util.List;

/**
 * Prim算法，第二版
 * 使用最小堆优先队列优化算法
 *
 * @author Minuy
 * @time 17:18
 * @date 2021/11/25
 */
public class PrimPQ {

    List<WeightedEdge> mst;

    public PrimPQ(WeightedGraph g) {

        mst = new ArrayList<>();

        WeightedCC cc = new WeightedCC(g);
        if (cc.count() != 1) {
            return;
        }

        // Prim算法：
        boolean[] isVisited = new boolean[g.V()];
        isVisited[0] = true; // 蓝色

        PriorityQueueMin<WeightedEdge> pq = new PriorityQueueMin<>();
        for (int v : g.adj(0)) {
            pq.enqueue(new WeightedEdge(v, 0, g.getWeight(v, 0)));
        }

        while (!pq.isEmpty()) {
            WeightedEdge edge = pq.dequeue();

            // 属于同一个切分
            if (isVisited[edge.w] == isVisited[edge.v]) {
                continue; // 如果不是横切边就可以直接下一个了
            }

            mst.add(edge);

            // 如果 v 是蓝色的，那 w 就是绿色的，否则 v 是绿色的
            int greenV = isVisited[edge.v] ? edge.w : edge.v;

            isVisited[greenV] = true;

            // 添加新的横切边到优先队列中
            for (int v : g.adj(greenV)) {
                pq.enqueue(new WeightedEdge(v, greenV, g.getWeight(v, greenV)));
            }
        }


//        for (int e=1;e<g.V();e++){ // 寻找v-1次最短横切边
//            WeightedEdge minEdge = new WeightedEdge(-1,-1,Integer.MAX_VALUE);
//            for (int v=0;v<g.V();v++){ // 遍历所有的顶点
//                if (isVisited[v]){ // 顶点是蓝色的
//                    for (int w:g.adj(v)){ // 看看是不是有绿色的顶点相邻
//                        if (!isVisited[w]){ // 绿色
//                            // w-v肯定是横切边
//                            WeightedEdge edge = new WeightedEdge(w,v,g.getWeight(w,v));
//                            minEdge = edge.compareTo(minEdge)<0?edge:minEdge;
//                        }
//                    }
//                }
//            }
//            // 在这就找到了最小的横切边
//            mst.add(minEdge);
//            isVisited[minEdge.w] = true; // 都变成蓝色的
//            isVisited[minEdge.v] = true;
//        }
    }


    /**
     * 获取最小生成树
     *
     * @return Iterable<WeightedEdge> 最小生成树的所有边
     * @author Minuy
     * @date 2021/11/25 16:47
     */
    public Iterable<WeightedEdge> mst() {
        return mst;
    }

    @Override
    public String toString() {
        return mst().toString();
    }
}
